//
// Created by francklinson on 2021/5/2.
//

/*你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和应该相等。

你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。
 你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。
 你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。


示例 1：

输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
输出：2

示例 2：
输入：wall = [[1],[1],[1]]
输出：3

提示：

n == wall.length
1 <= n <= 104
1 <= wall[i].length <= 104
1 <= sum(wall[i].length) <= 2 * 104
对于每一行 i ，sum(wall[i]) 应当是相同的
1 <= wall[i][j] <= 231 - 1*/
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int leastBricks(vector<vector<int>> &wall) {
        // 找出现最多的墙缝
        int total = accumulate(wall.begin()->begin(), wall.begin()->end(), 0); // 墙的宽度
        if (total == 1)return (int) wall.size();
        vector<int> counter(total - 1, 0); // 墙缝
        int full = 0; // 一块砖塞满一行
        for (const auto &row:wall) {
            int gap = -1;
            for (const auto &x:row) {
                if (gap == total) ++full;
                gap += x;
                ++counter[gap];
            }
        }
        return (int) wall.size() - *max_element(counter.begin(), counter.end() - 1) + full;
    }
};
class Solution2 { // 题解 hash代替vector  降低vector长度
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int, int> cnt;
        for (auto& widths : wall) {
            int n = (int)widths.size();
            int sum = 0;
            for (int i = 0; i < n - 1; i++) {  //最后一块不算
                sum += widths[i];
                cnt[sum]++;
            }
        }
        int maxCnt = 0;
        for (auto& x : cnt) {
            maxCnt = max(maxCnt, x.second);
        }
        return (int)wall.size() - maxCnt;
    }
};

int main() {
    vector<vector<int>> brick{{1, 2, 2, 1},
                              {3, 1, 2},
                              {1, 3, 2},
                              {2, 4},
                              {3, 1, 2},
                              {1, 3, 1, 1},
                              {6}};
    vector<vector<int>> brick2{
            {1},
            {1},
            {1}
    };
    Solution2 sol;
    cout << sol.leastBricks(brick) << endl;
    cout << sol.leastBricks(brick2) << endl;
    return 0;
}